package hard.区间问题.跳跃游戏;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 跳跃游戏 II
 * 这题比跳跃游戏难得多，这题可以采用动态规划，也可以采用贪心法
 * 面试的时候建议采用动态规划，更好理解 (方法1)
 * @date 2022/11/20 16:25
 */
public class Demo45 {
    
    public int jump(int[] nums) {
        if(nums.length==1){
            return 0;
        }
        //记录每个位置跳跃的步数
        int[] dp=new int[nums.length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        //起始位置是0，所以跳到这步的步数是0
        dp[0]=0;
        for (int i = 1; i < nums.length; i++) {
            //遍历i位置 前面的每一个位置
            for (int j = 0; j < i; j++) {
                //如果该位置的索引加上数值大于i的索引，计算最小步数
                if(nums[j]+j>=i){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[dp.length-1];
    }
    //方法二，贪心法
    public int jump2(int[] nums) {
        if(nums.length==1){
            return 0;
        }
        //记录每个位置跳跃的步数
        int step=0;
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            maxDistance=Math.max(maxDistance,nums[i]+i);
            //到头了,返回步骤
            if(maxDistance >= nums.length-1){
                step++;
                return step;
            }
            if(i==curDistance){
                curDistance=maxDistance;
                step++;
            }
        }
        return step;
    }
}
